//给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "leetcode"
//输出: 0
// 
//
// 示例 2: 
//
// 
//输入: s = "loveleetcode"
//输出: 2
// 
//
// 示例 3: 
//
// 
//输入: s = "aabb"
//输出: -1
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length <= 10⁵ 
// s 只包含小写字母 
// 
// Related Topics 队列 哈希表 字符串 计数 👍 554 👎 0


import java.util.*;

/**
 * [0387]字符串中的第一个唯一字符-FirstUniqueCharacterInAString
 * <p>
 * 算法: 哈希表/队列
 * <br>
 * 时间复杂度: O(n)
 * <br>
 * 空间复杂度: O(∣Σ∣)
 * <p>
 * 知识点:
 * <br>
 * 1. s.split("") 可以把数组分割成字符串数组    <br>
 * 2. String 的底层实现是 char[]    <br>
 * 3. 使用 s.toCharArray() 将字符串转换成数组, 比 s.split("") 性能大约提升了 10 倍    <br>
 * 4. 使用 s.charAt(i) 遍历字符串    <br>
 * 5. 队列:先进先出;    <br>
 * offer() 添加到队头,成功为 true,失败为 false;    <br>
 * peek() 获取队头, 如果队列为空返回 null;    <br>
 * poll() 获取队头并将队头从队列删除, 如果队列为空返回 null
 *
 * @author yonxao
 * @since 2022-05-30 18:49:05
 */
class FirstUniqueCharacterInAString {
    @SuppressWarnings("all")
//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int firstUniqChar(String s) {
            Map<Character, Integer> positionMap = new HashMap<>();
            Queue<Pair> queue = new LinkedList<>();

            int n = s.length();
            for (int i = 0; i < n; ++i) {
                char c = s.charAt(i);
                if (!positionMap.containsKey(c)) {
                    // k-字母/v-字母的索引
                    positionMap.put(c, i);
                    queue.offer(new Pair(c, i));
                } else {
                    positionMap.put(c, -1);
                    // 如果队列不为空 并且 队列头的字母的位置是 -1
                    while (!queue.isEmpty() && positionMap.get(queue.peek().c) == -1) {
                        queue.poll();
                    }
                }
            }
            return queue.isEmpty() ? -1 : queue.poll().position;
        }

        class Pair {
            char c;
            int position;

            Pair(char c, int position) {
                this.c = c;
                this.position = position;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        String s1 = "leetcode";
        String s2 = "loveleetcode";
        String s3 = "aabb";
        System.out.println(firstUniqChar2(s1));
        System.out.println(firstUniqChar2(s2));
        System.out.println(firstUniqChar2(s3));

    }

    /**
     * 算法: 用一个哈希表记录已经判过重的, 如果哈希表中不存在且与之后的不重复, 则返回索引值
     * <br>
     * 时间复杂度: O(n^2)
     * <br>
     * 空间复杂度: O(n)
     * <p>
     * 知识点: s.split("") 可以把数组分割成字符串数组
     * <br>
     */
    public static int first(String s) {
        String[] sa = s.split("");
        Set<String> set = new HashSet<>();
        for (int i = 0; i < sa.length; i++) {
            boolean flag = false;
            for (int j = i + 1; j < sa.length; j++) {
                if (sa[i].equals(sa[j])) {
                    flag = true;
                    break;
                }
            }

            if (!flag && !set.contains(sa[i])) {
                return i;
            }
            set.add(sa[i]);
        }
        return -1;
    }


    /**
     * 算法: 如果出现重复, 就把所有的这个字母都置为 null
     * <br>
     * 时间复杂度: O(n^2)
     * <br>
     * 空间复杂度: O(n)
     * <p>
     * 知识点:
     * <br>
     */
    public static int firstOptimize(String s) {
        String[] sa = s.split("");

        for (int i = 0; i < sa.length; i++) {
            boolean flag = false;
            for (int j = i + 1; j < sa.length; j++) {
                if (sa[i] == null) {
                    break;
                } else if (sa[i].equals(sa[j])) {
                    flag = true;
                    sa[j] = null;
                }
            }
            if (sa[i] != null && !flag) {
                return i;
            } else {
                sa[i] = null;
            }
        }
        return -1;
    }


    /**
     * 算法: 如果出现重复, 就把所有的这个字母都置为 null
     * <br>
     * 时间复杂度: O(nlogn)
     * <br>
     * 空间复杂度: O(n)
     * <p>
     * 知识点:
     * <br>
     * 1. String 的底层实现是 char[] <br>
     * 2. 使用 s.toCharArray() 将字符串转换成数组, 比 s.split("") 性能大约提升了 10 倍
     */
    public static int firstUniqChar(String s) {
        // 使用 s.toCharArray() 将字符串转换成数组, 性能大约提升了 10 倍
        char[] sa = s.toCharArray();

        for (int i = 0; i < sa.length; i++) {
            boolean flag = false;
            for (int j = i + 1; j < sa.length; j++) {
                if (sa[i] == '.') {
                    break;
                } else if (sa[i] == (sa[j])) {
                    flag = true;
                    sa[j] = '.';
                }
            }
            if (sa[i] != '.' && !flag) {
                return i;
            } else {
                sa[i] = '.';
            }
        }
        return -1;
    }

    /**
     * 算法: 哈希表
     * <br>
     * 时间复杂度: O(n)
     * <br>
     * 空间复杂度: O(∣Σ∣)
     * <p>
     * 知识点: 使用 s.charAt(i) 遍历字符串
     * <br>
     */
    public static int firstUniqChar2(String s) {
        int length = s.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, -1);
            } else {
                map.put(c, i);
            }
        }
        int first = length;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Integer i = entry.getValue();
            if (i != -1 && i < first) {
                first = i;
            }
        }
        return first == length ? -1 : first;
    }


    /**
     * 算法: 队列, 先进先出, 不符合条件就从队头删掉, 最后返回队头
     * <br>
     * 时间复杂度: O(n)
     * <br>
     * 空间复杂度: O(∣Σ∣)
     * <p>
     * 知识点:
     * <br>
     * 1. 队列:先进先出; <br>
     * offer() 添加到队头,成功为 true,失败为 false;<br>
     * peek() 获取队头, 如果队列为空返回 null; <br>
     * poll() 获取队头并将队头从队列删除, 如果队列为空返回 null
     */
    public int firstUniqChar3(String s) {
        Map<Character, Integer> positionMap = new HashMap<>();
        Queue<Pair> queue = new LinkedList<>();

        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            if (!positionMap.containsKey(c)) {
                // k-字母/v-字母的索引
                positionMap.put(c, i);
                // queue.offer() 如果可以在不违反容量限制的情况下立即将指定的元素插入到队列中。
                queue.offer(new Pair(c, i));
            } else {
                positionMap.put(c, -1);
                // 如果队列不为空 并且 队列头的字母的位置是 -1
                // queue.peek() 检索但不删除该队列的头部，如果该队列为空，则返回null
                while (!queue.isEmpty() && positionMap.get(queue.peek().c) == -1) {
                    // queue.poll() 检索并删除该队列的头部，如果该队列为空，则返回null。
                    queue.poll();
                }
            }
        }
        return queue.isEmpty() ? -1 : queue.poll().position;
    }

    static class Pair {
        char c;
        int position;

        Pair(char c, int position) {
            this.c = c;
            this.position = position;
        }
    }
}